package leetcode.pre50;

import offerbook.Code38_GetNumberOfKInSortArray;

import java.util.Arrays;

/**
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * <p>
 * 你的算法时间复杂度必须是 O(log n) 级别。
 * <p>
 * 如果数组中不存在目标值，返回 [-1, -1]。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: [3,4]
 * 示例 2:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: [-1,-1]
 * <p>
 * 同样的题：其他分析见
 * @see Code38_GetNumberOfKInSortArray
 *
 * @since 2019/11/23 0023 下午 10:47
 */
public class Code34_FindNumInSortArray {

    /**
     * 方式2：二分查找。递归版与分递归版都有
     */
    public static int[] searchRange(int[] arr, int target) {
        int []res = {-1,-1};
        if (!checkPass(arr, target)) {
            return res;
        }
     /*   res[0] = halfSearchLeft(arr,0,arr.length-1,target);
        res[1] = halfSearchRight(arr,0,arr.length-1,target);*/
        res[0] = halfSearchLeft1(arr,target);
        res[1] = halfSearchRight1(arr,target);
        return res;
    }

    private static int halfSearchLeft(int[] arr, int start,int end,int target) {
        if(start > end){
            return -1;
        }
        int mid = start + (end - start)/2;
        if(arr[mid] < target){
            return halfSearchLeft(arr,mid+1,end,target);
        }else if(arr[mid] > target){
            return halfSearchLeft(arr,start,mid-1,target);
        }else {
            if(mid == 0) return 0;
            if(arr[mid] != arr[mid - 1]) return mid;
            return halfSearchLeft(arr,start,mid-1,target);
        }
    }


    private static int halfSearchLeft1(int[] arr,int target) {
        int left = 0;
        int right = arr.length - 1;
        int mid = left + (right - left)/2;
        while (left <= right){
            if(arr[mid] == target){
                if(mid == 0) return 0;
                if(arr[mid] != arr[mid-1]) return mid;
                right = mid - 1;
            }else if(arr[mid] < target){
                left = mid + 1;
            }
            mid = left + (right - left)/2;
        }
       return -1;
    }

    private static int halfSearchRight(int[] arr, int start,int end,int target) {
        if(start > end){
            return -1;
        }
        int mid = start + (end - start)/2;
        if(arr[mid] < target){
            return halfSearchRight(arr,mid+1,end,target);
        }else if(arr[mid] > target){
            return halfSearchRight(arr,start,mid-1,target);
        }else {
            if(mid == arr.length - 1) return arr.length -1;
            // mid < arr.len -1
            if(arr[mid] == arr[mid+1])  //继续向右搜索
                return halfSearchRight(arr,mid+1,end,target);
            // arr[mid] != arr[mid+1]
            return mid;

        }
    }


    private static int halfSearchRight1(int[] arr,int target) {
        int left = 0;
        int right = arr.length-1;
        int mid = left + (right - left)/2;
        while (left <= right){
            if(arr[mid] == target){
                if(mid == arr.length - 1) return arr.length - 1;
                if(arr[mid] != arr[mid + 1]) return mid;
                left = mid + 1;
            }else if(arr[mid] > target){
                right = mid - 1;
            }
            mid = left + (right - left)/2;
        }
        return -1;
    }

    /**
     * 方式1：O(n),找到第一个索引和最后一个索引
     */
    private static boolean checkPass(int arr[], int target) {
        if (arr == null || arr.length == 0 || target < arr[0] || target > arr[arr.length - 1]) {
            return false;
        }
        return true;
    }

    public static int[] getCountOfK(int arr[], int target) {
        int []res = {-1,-1};
        if (!checkPass(arr, target)) {
            return res;
        }
        for (int i = 0; i < arr.length; i++) {
            if(i > 0 && arr[i] == target && arr[i-1] != target
                    || i == 0 && arr[i] == target){
                res[0] = i;
            }
            if(i < arr.length - 1 && arr[i] == target && arr[i+1] != target
                    || i == arr.length - 1 && arr[i] == target){
                res[1] = i;
                return res;
            }

        }
        return res;
    }

    public static void main(String[] args) {
        int []arr = {5,7,7,8,8,10};
        int target = 8;
        getCountOfK(arr,target);
        int[] ints = searchRange(arr,target);
        System.out.println(Arrays.toString(ints));
    }
}
